Exemplary embodiments relate to communications, and more specifically, to scanning for patterns.
Packet scanning, also known as packet content scanning, is an important part of network security and application monitoring. Packets in a stream are mapped against a set of patterns to detect security threats or to gain information about the stream or packet stream. Due to their flexibility, regular expressions are a common way to define such patterns. Finite automata are typically used to implement regular expression scanning or parsing.
In contrast to Non-Deterministic Finite Automata (NFA), Deterministic Finite Automata (DFA) only requires one state transition per input value. This yields higher scanning or parsing rates and a smaller parse state which has to be maintained per flow. Therefore, DFA are utilized for Network Intrusion Detection Systems (NIDS) although they usually require more memory than NFA. Regular expressions can be compiled into NFAs and DFAs using well-known techniques.
Regarding NIDS, the frequency of network attacks increases every year, and the methods of attack are becoming more sophisticated. NIDS works to keep up with these trends. NIDS can apply very powerful and flexible content-filtering rules defined using regular expressions. This has triggered a substantial amount of research and product development in the area of hardware-based accelerators for pattern matching, as this seems to be a viable approach for scanning network data against the increasingly complex regular expressions at wire-speed processing rates of tens of gigabits per second.
Moreover, in typical network environments, the number of open sessions at any given time can be on the order of millions, and the streams are scanned in an interleaved fashion. Therefore, the internal state of the scanning engine has to be stored and reloaded whenever the input stream is switched.